This present invention relates to decoding and more particularly to an efficient scheme for decoding in multiple access communications channels.
The explosive growth in the demand for wireless communications has been a phenomenal and worldwide event. There are already over 500 million users that subscribe to cellular telephone services and the number is increasing exponentially. The advantages of wireless tools are obvious, and the number of cellular subscribers will soon exceed the number of fixed line telephone installations. Cellular usage is beginning to become the primary phone option, and as more and more content and wireless tools become available, the increase will continue to expand and proliferate across the globe.
In addition to the explosion of cellular usage, there are other wireless implementations such as Internet access, messaging, paging, wireless local area networks (WLANs). With respect to cellular services, the vast majority of users currently subscribe to digital cellular networks, and the typical state of the art cellular handset is based on digital technology such as GSM, TDMA (IS-136) or CDMA (IS-95), although the legacy analog systems using protocols AMPS and TACS are still in operation.
New, emerging receiver processing procedures allow for huge increases in the utilization of multiple access communications, especially in the wireless sector. The tremendous growth and for wireless cellular phones, wireless personal digital assistants (PDA""s), laptops and mobile tablets demonstrates the huge volume of traffic and the varying content desired by the public. There are a number of protocols established to define the bandwidth characteristics, including 3G, IEEE 802.11, and Bluetooth, however the number of users and devices requires more users than available bandwidth. The ability to access data and communicate anywhere at anytime has enormous potential and commercial value.
The content of the wireless sector is also changing, with more and more data being transmitted, including Internet connectivity and live feeds. The usage involving personal digital assistants (PDA""s) and even smart appliances have created new markets utilizing wireless data communications. And, this wireless phenomenon is not limited to any geographical boundaries, as the growth is occurring around the globe.
Thus, despite the advancements in wireless transmission and reception, there is a growing problem of extracting more information signals within a limited bandwidth. Emerging multiple-access receiver processing procedures allow for multiple users to access the same communications medium to transmit or receive information. In addition to the problems associated with multiple users in a given bandwidth, an additional problem is the inability to process the data in the receivers in real time. Advanced receiver techniques cover several areas, namely interference suppression (also called multi-user detection), multipath combining and space-time processing, equalization, and channel estimation. These various techniques can be mixed and matched depending upon the circumstances. Proper signal processing of transmitter and receiver yield a far greater potential than current systems.
While the discussion herein illustrates wireless communications, the multiple access topology is equally applicable to wired cable systems and local area networks, read/write operations of a disc drive, satellite communications and any application that benefits from processing of digital data from among many multiple sources. The use of the term xe2x80x98usersxe2x80x99 is therefore utilized as a convention to describe processing among a plurality of signal sources.
The entire field of digital communications encompasses some sophisticated processing and is deployed in a wide range of applications and electronics. Digital communication techniques are now used for communication of combined audio and video telephony. Communication networking also has exploded as affordable connectivity with greater bandwidth has become available via WiFi, satellite, modulated communications over power lines, cable connections, telephone connections and various hybrid systems.
Regardless of the manner in which the communications are delivered, reliable communications are essential. The quality of the communications depends upon the accuracy with which the transmitted signals match the received signals. While some forms of communications, such as audio, can withstand significant bit loss, digital data communications require greater fidelity in order to be successfully processed. Error control coding is used to provide the required fidelity in the presence of channel noise without increasing the power of the transmitted signal.
Terrestrial and satellite radio systems operate over RF propagation channels that induce signal waveform and spectrum distortions, including signal attenuation and multi-path fading. These applications generally use a Forward error correction (FEC) and are designed according to factors such as modulation formats, error control schemes, demodulation and decoding techniques and hardware components to optimize system performance and implementation complexity. Advanced techniques such as multi-user detection and error correction are also used in applications other than wireless communications and data networking systems. For example, the storage and subsequent retrieval of stored computer data utilizes error correction techniques to ensure exact fidelity of the data. Equipment such as compact disc players, digital audio tape recorders and players also employ error correction techniques to provide high fidelity output. However, for convenience, a further discussion of multiple access wireless communications is included herein to describe processing of data with error corrections.
Existing wireless communication systems generally employ a match between the transmitter encoding and the receiver decoding schemes. The transmitter typically incorporates one or more encoders, one or more interleavers, a symbol generator (i.e. bit to symbol mapper) and modulator. Input data bits to be transmitted are input to the encoder that can encompass one of the various error correction encoders such as Reed Solomon, convolutional encoder, and parity bit generator. The function of each encoder is to add redundancy to enable detection and/or correction of errors in transmission. The output bits from the encoder may then be interleaved wherein the order of the bits is changed to more efficiently combat burst errors. The re-arrangement of the bits caused by interleaving improves the resistance to error bursts while adding latency and delay to the transmission. The first encoder is called the outer encoder and the second encoder is called the inner encoder. The purpose of applying two encoders rather than one (more complex) more powerful code is to reduce the decoding complexity required at the receiver while combating the effects of different types of transmission errors, such as burst errors caused by channel fading as well as random bit errors caused by white noise.
The output bits from the second interleaver are then mapped to symbols by a bit to symbol mapper, wherein the bit to symbol mapper transform the bits to modulator symbols. For example, an 8-PSK (phase-shift keying) modulator uses 8 symbols and the mapper takes three bits and converts them to one of eight symbols. Thus, the bit to symbol mapper generates a symbol for every three input bits in that example.
The output from the symbol mapper is input to a modulator that receives symbols in the M-ary alphabet and generates the analog signal that is subsequently transmitted over the channel by an antenna in wireless applications. The channel may comprise a mobile wireless channel, such as cellular or satellite. There can also be hard wired channel, such as a cable such as Ethernet. The industry strives to employ a transmitter that generates a signal in such a way that it is correctly reconstructed by the receiver.
At the receiver, the analog signal from the channel is input to a front end section that demodulates and samples the received signal to generate received samples y(k). There can also be amplification and filtering at the receiver to boost signal levels and eliminate or reduce noise components. The samples are input to a signal processor such as an equalizer that compensates for the inter-symbol interference (ISI) caused by the delay and time spreading of the channel in attempting to detect the symbols transmitted by the modulator.
In a CDMA system, each signal is transmitted using spread spectrum techniques. The transmitted informational data stream is impressed upon a much higher rate data stream termed a signature sequence. The bit stream of the signature sequence data is typically binary, and can be generated using a pseudo-noise (PN) process that appears random, but can be replicated by an authorized receiver. The informational data stream and the high bit rate signature sequence stream are combined by multiplying the two bit streams together, assuming the binary values of the two bit streams are represented by +1 or xe2x88x921. This combination of the higher bit rate signal with the lower bit rate data stream is called spreading the informational data stream signal. Each informational data stream or channel is allocated a unique signature sequence.
In operation, a plurality of spread information signals, such as binary phase shift keying (BPSK) or quadrature phase shift keying (QPSK) modulation, modulate a radio frequency (RF) carrier and are jointly received as a composite signal at the receiver. Each of the spread signals overlaps all of the other spread signals, as well as noise-related signals, in both frequency and time. The receiver correlates the composite signal with one of the unique signature sequences, and the corresponding information signal is isolated and despread.
A signature sequence is normally used to represent one bit of information. Receiving the transmitted sequence or its complement indicates whether the information bit is a +1 or xe2x88x921, sometimes denoted xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. The signature sequence usually comprises N pulses, and each pulse is called a xe2x80x9cchipxe2x80x9d. The entire N-chip sequence, or its complement, depending on the information bit to be conveyed, is referred to as a transmitted symbol. The receiver correlates the received signal with the complex conjugate of the known signature sequence to produce a correlation value. When axe2x80x98largexe2x80x99 positive correlation results, a xe2x80x9c0xe2x80x9d is detected, and when axe2x80x98largexe2x80x99 negative correlation results, a xe2x80x9c1xe2x80x9d is detected.
It should be understood that the information bits could also be coded bits, where the code is a block or convolutional code. Also, the signature sequence can be much longer than a single transmitted symbol, in which case a subsequence of the signature sequence is used to spread the information bit.
Multipath dispersion occurs when a signal proceeds to the receiver along not one but many paths so that the receiver encounters echoes having different and randomly varying delays and amplitudes. Co-channel interference refers to signals received from other users either directly or reflected. The receiver receives a composite signal of multiple versions of the transmitted symbol that have propagated along different paths, called rays, having different relative time. Each distinguishable ray has a certain relative time of arrival, a certain amplitude and phase, and as a result, the correlator outputs several smaller spikes. RAKE receivers are well known and attempt to xe2x80x98rakexe2x80x99 together all the contributions to detect the transmitted symbol and recover the information bit.
Conventional RAKE receivers provide satisfactory performance under ideal conditions, however the signature sequence must be uncorrelated with time shifted versions of itself as well as various shifted versions of the signature sequences of the other CDMA signals. If one received signal corresponding to the signature sequence of interest has a non-negligible cross correlation with the received signal originating from another transmitter, then the value measured at the receiver, e.g. the correlation value for the signal of interest, is corrupted. In other words, the correlation computed at the receiver that would be used to decode a particular signal of interest is overwhelmed by an interfering signal; this is referred to as the near-far problem. The interference caused by an echo of one transmitted symbol overlapping with the next transmitted symbol must also be negligible. If this is not true, the transmitted symbols interfere with past and future transmitted symbols, commonly referred to as intersymbol interference (ISI). In actuality, performance is degraded by other signal interference and ISI.
There has been much research to address signal interference with known multipath time dispersion. This is termed joint demodulation with no multipath and is further described in S. Verdu, xe2x80x9cMinimum Probability of Error For Asynchronous Gaussian bMultiple-Access Channels,xe2x80x9d IEEE Trans. Info. Theory, Vol. IT-32, pp. 85-96, R. Lupas and S. Verdu, xe2x80x9cLinear multiuser detectors for synchronous code-division multiple-access channels,xe2x80x9d IEEE Trans. Inform. Theory, Vol. 35, pp. 123-136, Jan. 1989; and R. Lupas and S. Verdu, xe2x80x9cNear-far resistance of multiuser detectors in asynchronous channels,xe2x80x9d IEEE Trans. Commun., Vol. 38, pp. 496-508, April 1990.
There are a host of approaches for jointly demodulating any set of interfering digitally modulated signals, including multiple digitally modulated signals. Maximum Likelihood Sequence Estimation determines the most likely set of transmitted information bits for a plurality of digital signals without multipath time dispersion. The maximum likelihood joint demodulator is capable, in theory, of accommodating the largest number of interfering signals, but has a prohibitive computational complexity that makes it unrealizable in practice. The decorrelation receiver is another, less computationally complex receiver processing approach that zeroes out or decorrelates the different signals so that they no longer interfere with one another. The decorrelator, as well as virtually every other lower complexity joint demodulator, is not capable of operation when the number of signals is over a set threshold which falls significantly short of the theoretical maximum.
In a real world multi-user system, there are a number of independent users simultaneously transmitting signals. These transmissions have the real-time problems of multi-path and co-channel interference, fading, and dispersion that affect the received signals. As described in the prior art, multiple user systems communicate on the same frequency and at the same time by utilizing parameter and channel estimates that are processed by a multi-user detector. The output of the multi-user detector is an accurate estimation as to the individual bits for an individual user.
Multi-user detection (MUD) refers to the detection of data in non-orthogonal multiplexes. MUD processing increases the number of bits available per chip or signaling dimension for systems having interference limited systems. A MUD receiver jointly demodulates co-channel interfering digital signals.
Optimal MUD based on the maximum likelihood sequence estimator operates by comparing the received signal with the entire number of possibilities that could have resulted, one for each bit or symbol epoch. Unfortunately, this processing is a computationally complex operation and it is not possible to accomplish in a real-time environment. Thus for those multi-user detectors that examine the entire space, real-time operation is often elusive.
In general, optimal MUD units function by examining a number of possibilities for each bit. However, for multi-user detectors that examine a larger capacity of signal, the computations are complex and time-consuming, thus making real-time operation impossible. Numerous attempts at reliable pruning of the optimal MUD decision process or the use of linear approximation to the replace the optimal MUD have still not produced a workable solution for the real world environment.
There are various multiuser detectors in the prior art, including optimal or maximum likelihood MUD, maximum likelihood sequence estimator for multiple interfering users, successive interference cancellation, TurboMUD or iterative MUD, and various linear algebra based multi-user detectors such as all of those detailed in the well-know text xe2x80x9cMultiuser Detectionxe2x80x9d by Sergio Verdu. In basic terms, turbodecoding refers to breaking a large processing process into smaller pieces and performing iterative processing on the smaller pieces until the larger processing is completed. This basic principle was applied to the MUD.
There are several suboptimal multiuser detectors that are less computationally complex. One example of suboptimal detectors, called linear detectors, includes decorrelators, minimum mean square error or MMSE detectors, and zero-forcing block linear equalizers. But, linear algebra based MUD (non-iterative) and successive interference cancellation fails for cases of overloaded multiple access systems. One example of overloading is where the number of simultaneous users is doubled relative to existing state of the art. Even for underloaded multiple access systems, the performance of non-iterative MUD and successive interference cancellation degrades significantly as the number of users increases, while the computation complexity of the optimal MUD increases significantly as the number of users increases. The computing problems are so extreme that it requires extensive and expensive hardware as well as complex processing. Moreover, an unreasonable delay would be required to decode each bit or symbol rendering such a system useless in practice.
Low complexity multiuser detectors have been contemplated that use linear multiuser detectors to achieve optimal near-far resistance. (Near-Far Resistance of Multiuser Detectors for Coherent Multiuser Communications, R. Lupas, S. Verdu, IEEE Trans. Commun. Vol 38, no. 4, pp 495-508, April 1990). While providing certain advantages, the performance has not been demonstrably improved. Varanasi and Aazhang proposed a multistage technique as described in the article Near-Optimum Detection in Synchronous Code-Division Multiple Access Systems, IEEE Trans. Commun., vol 39, No. 5, May 1991.
Decorrelating decision feedback detectors (DDFD) have been described by A. Duel-Hallen in Decorrelating Decision-Feedback Multiuser Detector for Synchronous Code-division Multiple Access Channel, IEEE Trans. Commun., vol 41, pp 285-290, February 1993. Wei and Schlegel proposed soft-decision feedback to suppress error propagation of the DDFD in Synchronous DS-SSMA with Improved Decorrelating Decision-Feedback Multiuser Detection, IEEE Trans. Veh. Technol., vol 43, pp 767-772, August 1994.
Another reduced complexity MUD general approach is based on tree-pruning help to some extent to eliminate the proper bit combination from consideration (i.e. prune the proper path in the decision tree) based on information from an unreliable bit estimate. For instance, the M-algorithm is a pruning process that limits the number of hypotheses extended to each stage to a fixed tree width and prunes based on ranking metrics for all hypotheses and retaining only the M most likely hypotheses. The T-algorithm prunes hypotheses by comparing the metrics representing all active hypotheses to a threshold based on the metric corresponding to the most-likely candidate. Performance of M-algorithm based MUD degrades as the parameter M is decreased, but M governs the number of computations required. Similar effects and tradeoffs are seen for other tree-pruning based MUD (T-algorithm, etc). To combat improper pruning, basic tree-pruning must ensure that M is xe2x80x9clarge enoughxe2x80x9d, and therefore still encounters increased complexity for acceptable performance levels when the number of interfering signals and/or ISI lengths are moderate to large.
An illustration of the M-algorithm as a tree-pruning algorithm is a tree made up of nodes and branches. Each branch has a weight or metric, and a complete path is sequences of nodes connected by branches between the root of the tree and its branches. When applied as a short cut to the optimal MUD, each branch weight is a function of the signature signal of a certain transmitter, the possible bit or symbol value associated with that transmitter at that point in time, and the actual received signal which includes all the signals from all the interfering transmissions. The weight of each path is the sum of the branch metrics in a complete path. The goal of a tree searching algorithm is to try to find the complete path through a tree with the lowest metric.
In an article by Paul D. Alexander, Mark C. Reed, John A. Asenstorfer and Christian B. Schlagel in IEEE Transactions on Communications, vol. 47, number 7, July 1999, entitled xe2x80x9cIterative Multi-User Interference Reduction: Turbo CDMAxe2x80x9d, a system is described in which multiple users transmit coded information on the same frequency at the same time, with the multi-user detection system separating the scrambled result into interference-free voice or data streams.
The turboMUD system applies the xe2x80x9cturbo principlexe2x80x9d by modeling the multiuser channel as a convolutional code, thereby modeling the overall transmitted system as a serial concatenation of two convolutional codesxe2x80x94the actual error correction code and the effects of the modulation and multi-user interference. A MUD algorithm within the TurboMUD system determines discrete estimates of the transmitted channel symbols, with the estimates then provided to a bank of single-user decoders (one decoder for each user) to recover the input bit streams of all transmitted signals. If two codes were employed at the transmitter, the prior art TurboMUD uses the second error correction code and the channel to form a decoding turbo-loop. The outer decoder is simply applied after the TurboMUD is complete.
In an attempt to provide real-time performance by reducing the computational complexity of an iterative multi-user detector that can produce soft values, the prior references suggests algorithms for examining less than the total number of possibilities for each of the bits of data that are coming in from the multiple users. The xe2x80x9cshortcutsxe2x80x9d taken by this reduced complexity approach cause errors and combating these errors by increasing the number of iterations of the system completely nullifies any advantage.
Generally, error control coding expands the information sequence by adding additional bits for error correction/detection. The encoded sequence then contains some constraint or redundancy that is used by the receiver to identify possible errors in the received sequence. For example, if the received sequence does not satisfy parity-check equations, then the receiver detects the existence of some possible errors and corrects them according to the parity check rule. In other words, error correcting codes insert redundancy into digital information streams at the transmitter, thereby reducing susceptibility to noise and increasing receiver reliability. Incorporating error correcting coding at the transmitter allows the receiver to detect and possibly correct errors caused by noise or interference. Various error detection and correction (EDAC) techniques have been developed that effectively enable digital communications despite error rates inherent in digital communications.
Error control codes such as block codes and convolutional codes are usually applied to digital sequences expected to encounter burst and random errors, so that some portion of the errors may be corrected at the receiver. For example, the powerful Reed-Solomon EDAC provides the ability to correct multiple bit errors in high-noise interference environments such as critical space communications. Reed-Solomon coding originated in the article entitled: xe2x80x9cPolynomial Codes over Certain Finite Fieldsxe2x80x9d and uses Galois Field arithmetic to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block.
It should be understood that convolutional codes are somewhat inefficient at a handling large number of consecutive errors. In order to combat burst error in channels, system transmitters typically apply a block code before the convolutional code, so that the matching receiver must apply a block decoder after convolutional decoding. The block code recognizes an error condition and realizes certain erasures or indeterminate bits, depending on decoding sequence wherein the code. For a certain minimum number of erasures, it is able to correct for the indeterminate bits, as the block code operates according to expected results depending upon the decoding method. The block decoding calculates some number that matches the code book set which indicates the expected bits at certain location, and generates a flag if the expected bits do not match the code book set. For example, if the decoding processing knows that the book set can only have xe2x80x9810101 . . . xe2x80x99 and the decoded bit stream is xe2x80x9801101 . . . xe2x80x99, a flag is generated indicating a possible error condition of the first two bits.
One way to create the redundancy needed for error correction is by appending additional bits to fixed-length blocks of source data and transmitting the composite signal at a higher data rate. Alternatively, trellis codes, such as convolutional codes, can add redundancy by outputting specific sequences based on the encoder memory state and current incoming bits. Each transmitted symbol represents not only the current uncoded bit or set of bits, but also contains historical information, reflected in state information that can be derived from the received sequence of symbols. This redundancy permits the transmitted symbol sequence to be accurately reconstructed in a decoding operation even though noise and distortion have altered the message-bearing signal during transmission.
A concatenation of two error correcting codes is sometimes implemented through the use of a concatenated encoding system and a corresponding concatenated decoding system in order to lower the BER to acceptable levels without exponentially increasing the decoder complexity. Concatenated coding refers to the sequence of coding in which a second coding operation is performed upon already encoded data. An xe2x80x9couter codexe2x80x9d of the concatenated coding is the first code applied at the transmitter, while the xe2x80x9cinner codexe2x80x9d of the concatenated coding is the code applied second at the transmitter. Then at the receiver, the decoding process for the inner code is done first, followed by the decoding needed for the outer code.
Combining block coding, such as Reed-Solomon, and convolutional coding correct both burst and random errors in a continuous stream of convolved data bits. The block coding corrects for burst errors while the convolutional coding corrects random errors.
Interleaving is often placed between the two encoders, because when the inner decoder makes erroneous decisions, it tends to create bursts of errors due to the nature of the convolutional code. The interleaving disperses adjacent bit values and prevents a burst error from affecting a sequential run of bits in the original data stream.
Parallel concatenated convolutional codes (PCCC""s) or turbo codes have been shown to provide enhanced performance. The use of Turbo codes for error correcting has also enhances the reception capabilities of signals in less than perfect envirornents. The Turbo codes involve an iterated combination of two or more recursive systematic convolutional codes, where the codes of the encoder output bits include unaltered input bits. The convolutional codes are typically identical and applied to an input bit sequence and an interleaved version of the input bit sequence. In the case of continuous data transmission, turbo coding requires that the data stream be packetized into blocks for processing an entire message by blocks of N data bits.
Turbo codes use an iterated decoding technique wherein each successive decoding step outputs soft decisions usable as input to the next decoding step. The output of the encoder comprises systematic bits, the input bit sequence itself, and parity bits that can be punctured to provide a desired rate of encoding. By employing Turbo codes, the processing can approach the limit of channel capacity in the presence of noise set by the Shannon theorem. The performance of a Turbo Code depends on a number of factors such as the constituent codes, interleaver, information block size and number of decoder iterations. The factors can be tweaked for optimal processing for a particular application. For further details, see C. Berrou et al. entitled xe2x80x9cNear Shannon Limit Error-Correcting Coding And Decoding: Turbo-Codesxe2x80x9d, Proceedings of the IEEE International Conference on Communications, 1993, pages 1064-1070; and Hagenauer, Iterative Decoding of Binary Block and Convolutional Codes, IEEE Transactions on Information Theory, Vol. 42, No. 2 (March 1996).
A typical Turbo encoder uses a parallel concatenation of two systematic and recursive convolutional codes separated by interleaving. The turbo principal originally applied to two codes specifically designed for concatenated operation, has also been applied to other coding environments. For exarnple, the turbo principal was used to develop an error correction coding scheme using three component codes in the paper S. Benedetto, D. Divsalar, G. Montorsi, F. Pollara, in xe2x80x9cAnalysis, Design and Iterative Decoding of Double Serially Concatenated Codes with Interleaversxe2x80x9d, IEEE Journal on Selected Areas in Commnunications, vol 16, no 2, February 1998. Benedetto et al proposed and designed a doubly serially concatenated coding system in which three encoders, all of the same type and all designed specifically to operate well with each other, are concatenated. At the receiver, the turbo principal is applied sequentially to the inner, middle and outer codes to decode the received signal. This double serially concatenated approach addresses the scenario wherein the concatenated codes are either all block codes or all convolutional codes for the inner, middle and outer codes.
The xe2x80x9cturbo principlexe2x80x9d or xe2x80x9cturbo decodingxe2x80x9d refers to the iterative decoding method originally developed for turbo codes, which consist of carefully designed serial-concatenated or parallel-concatenated codes known in the art. The Turbo decoding method is used to achieve high performance for general (non-turbo-coded systems) with concatenated codes or concatenated elements. While usually employed for single users, it is noted that the effects of multiuser interference can be considered a code-like operation and that a multiuser system with error correction coding benefits from an iterative turbo decoding approach. For example, turboMUD, as described herein, applies the turbo principal to a multiuser interference channel, one convolutional code and one optional interleaver. The channel is modeled as a code and even though the system and components are not a designed turbo code, a turbo loop at the receiver improves the bit error rate performance of the system. For instance, Herzog, Schmidbauer, Hagenauer, xe2x80x9cIterative Decoding and Despreading improves CDMA-Systems using M-ary Orthogonal Modulation and FECxe2x80x9d, Proceedings of ICC 97 showed that turbo decoding provides performance gains of more than 1.5 dB over non-iterative decoding for the CDMA system that was examined. Additionally, certain methods to reduce the complexity of the MUD turbo decoding (xe2x80x9cturboMUDxe2x80x9d) have been utilized and are generally successful with the limitations and disadvantages noted herein.
The growing demand for error-free processing of digital signals requires an improvement to the detection and decoding techniques, especially a multi-user environment. What is needed is a practical and workable scheme that improves the bit error rate performance and allows for the reception and detection of a greater number of signals within a limited bandwidth and with greater reliability.
The invention is devised in the light of the problems described herein, and a general object of the present invention to provide a novel and useful decoding technique that can solve the problems noted in the existing systems.
Thus, this present invention addresses the problems associated with decoding in multiple access communications channels. The new method decreases the likelihood of improper decoding of the final values of interest, thereby allowing for a reduction in the number of iterations performed and, therefore, a reduction in complexity without negatively impacting performance. For the same reduced complexity MUD parameters and number of iterations, the present invention provides for superior performance when compared to other reduced-complexity MUD known in the art, followed by a separate decoder for the additional component(s).
One aspect of the invention is the incorporation of the results of additional decoder components into the iterative decoding process to improve the performance of a multiuser detector/decoder. Another aspect is applying a chained multi-turbo approach to a system with dissimilar components, such as one convolutional code, one block code and one component resembling a convolutional code caused by multi-user interference.
The subject of the invention disclosed in this application does not require that the signals correspond to any particular multiple access (MA) scheme, or any limitation to wireless processing. For example, the present invention operates in the same manner on any set of digitally modulated interfering signals to include cellular CDMA systems, TDMA systems, FDMA systems, storage medium, wired MA systems such a cable modems, wireless local area network systems, or yet undetermined systems. For example, Spatial Division Multiple Access (SDMA) is generally a satellite communications mode that optimizes the use of radio spectrum and minimizes system cost by taking advantage of the directional properties of dish antennas, and benefits from the bit processing described herein. The only requirement for viable operation of the present invention is that each signal source produces a signal with the information digitally modulated using a signature pulse or finite duration signal of some sort. While CDMA is described for illustrative purposes to explain the invention, the specific example of CDMA is merely for ease of understanding. The present invention is directed to any other form of digital communication or signal storage methods by simply replacing the words in the CDMA discussions xe2x80x9csignature sequencexe2x80x9d with xe2x80x9csignature signalxe2x80x9d or xe2x80x9csignature pulsexe2x80x9d and replacing the words xe2x80x9cCDMA signalxe2x80x9d with xe2x80x9cdigitally modulated signalxe2x80x9d.
A further feature of the present invention is that it works equally well using mixed rate communication systems such as IS95, wherein the user chooses the transmission rate. The parameter estimator that handles the differing transmission rates passes along the information to the present system.
Based upon the performance results of turboMUD methods and the recognition that topologies like the Astrolink system using GSM, IS-95 system, and other communication methods have two or more serially concatenated codes in their transmission processing chain, as well as a channel that can be modeled as a convolutional code, the present invention incorporates multiple codes in a turbo-decoding receiver. For example, state of the art decoders contain a Reed-Solomon (RS) block code in addition to a convolutional code and multiuser interference that are typically addressed by the turboMUD. The state of the art decoders for such systems use a straightforward partitioned (non-iterative) way of decoding the RS code at the receiver by simply appending a bank of RS decoders to the turboMWD unit.
The present invention in one embodiment is a multi-user detector processing system for multiple access communications channels, comprising a multi-user detector coupled to a plurality of user signals, wherein the multi-user detector produces a first set of symbol estimates for each of the user signals. There is a first bank of decoders coupled to the symbol estimates producing a first decoded data stream, and a second bank of decoders coupled to the first bank of decoders processing the first decoded data stream and producing a second decoded data stream, wherein the second decoded data stream is passed back to the first bank of decoders for processing of a third decoded data stream, and wherein the third decoded data stream is passed back to the multi-user detector for processing of a second set of symbol estimates for each of the user signals.
The multi-user detector of the multi-user detector processing system can employ, for example, algorithms selected from the group comprising M-algorithm, T-algorithm, MT algorithm, Q-algorithm, and FANO algorithm. The Q-algorithm is disclosed in U.S. patent application Ser. No. 10/105,918, filed Mar. 25, 2002 entitled xe2x80x9cSystem for Decreasing Processing Time in an Iterative Multi-User Detector Systemxe2x80x9d which is incorporated by reference herein for all purposes.
In one variation the first bank of decoders are convolutional decoders and the second bank of decoders are block decoders. In another variation the first bank of decoders are convolutional decoders and the second bank of decoders are convolutional decoders. And in a further variation the first bank of decoders are block decoders and the second bank of decoders are block decoders.
The convolutional decoders of the multi-user detector processing system can be, for example, selected from the group comprising maximum a posteriori (MAP) decoders, soft-output Viterbi algorithm (SOVA) decoders, and Bahl, Cocke, Jelinek, Raviv (BCJR) decoders.
In certain embodiment the multi-user detector processing system may include an interleaver and a de-interleaver coupled between the multi-user detector, the first bank of decoders and the second bank of decoders.
The multi-user detector processing system can also include a hard decision unit coupled to the low complexity bank of decoders processing the soft data stream producing a final data stream for each of the user signals.
Another embodiment for the multi-user detector processing system includes a filter unit coupled to the user signals and the multi-user detector, wherein the filter unit can be selected from the group comprising a whitening matched filter bank and a matched filter bank.
A further variation on the multi-user detector processing system includes further iterative processing of the second set of symbol estimates by the first bank of decoders and the second bank of decoders. The iterative processing continues until a final condition is obtained, wherein the final condition can be selected from the group comprising an allowable performance level and a fixed number of iterations.
The present invention includes an embodiment for a method for processing receiver signals from multiple users, wherein the method comprises estimating a set of symbols from the receiver signals for each of the users using a multi-user detector; decoding the set of symbols using a first decoder and producing a set of corrected first decoder values; decoding the first decoder values with a second decoder and producing a set of corrected second decoder values; decoding the set of corrected second decoder values using the first decoder and producing a set of re-corrected first decoder values; and, re-estimating the set of symbols using the re-corrected first decoder values.
The method can further comprise repeating the steps of decoding the set of symbols using the first decoder and decoding the first decoder values with the second decoder until a final state is obtained and outputting a final data stream for each user. The final state can be determined by setting a fixed number of iterations or by setting an allowable performance level.
Other variations can include performing parameter estimation of the receiver signals, filtering the receiver signals and also de-interleaving and interleaving.
In one respect the present invention is a Turbo Multi-User Detector for processing a plurality of received signals, comprising a parameter estimation unit coupled to the received signals and a multi-user detector coupled to the parameter estimation unit. The multi-user detector provides a plurality of information streams, one stream corresponding to each of the received signals. There is a bank of convolutional decoders coupled to the plurality of information streams, wherein the convolutional decoders output a plurality of refined information streams. There is also a bank of block decoders coupled to the plurality of refined information streams, wherein the block decoders output a plurality of refined-improved information streams, wherein the plurality of refined-improved information streams are fed back to the bank of convolutional decoders output a plurality of further refined-improved information streams which are fed back to the multi-user detector.
The Turbo Multi-User detector can further comprise an iterative processing between the multi-user detector, the bank of convolutional decoders and the bank of block decoders until a final condition is reached and the bank of block decoders output a final plurality of symbol streams.
The features and advantages described herein are not all-inclusive and, in particular, many additional features and advantages will be apparent to one of ordinary skill in the art-in view of the drawings, specification, and claims. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and not to limit the scope of the inventive subject matter.